// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-25 10:29
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class LinkForwardStar {
    int N = 100010, M = 2 * N, idx = 0;
    int[] head = new int[N];
    int[] to = new int[M];
    int[] edge = new int[M];

    void add(int a, int b) {
        edge[idx] = head[a];
        to[idx] = b;
        head[a] = idx++;
    }

    /**
     * 使用链式前向星记录图中数据
     */
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        Arrays.fill(head, -1);
        Arrays.fill(to, -1);
        Arrays.fill(edge, -1);
        for (int[] ints : edges) {
            add(ints[0], ints[1]);
            add(ints[1], ints[0]);
        }
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(0);
        int[] dist = new int[N];
        Arrays.fill(dist, -1);
        dist[0] = 0;
        while (!deque.isEmpty()) {
            Integer root = deque.poll();
            for (int i = head[root]; i != -1; i = edge[i]) {
                int j = to[i];
                if (dist[j] != -1) {
                    continue;
                }
                dist[j] = dist[root] + 1;
                deque.offer(j);
            }
        }
        int max = 0;
        for (int i = 0; i < patience.length; i++) {
            int d = dist[i] * 2, t = patience[i];
            int cur = d < t ? d : (d - 1) / t * t + d;
            if (cur > max) {
                max = cur;
            }
        }
        return max + 1;
    }


}
